package tree;

/**
 * 给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
 * 该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
 * 如果不存在祖父节点值为偶数的节点，那么返回 0 。
 * <p>
 * ex.:
 * 输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
 * 输出：18
 * 解释：图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。
 *
 * @author Jisheng Huang
 * @version 20250422
 */
public class SumEvenGrandparent_1315 {
    static int ans = 0;

    /**
     * Given a root tree node, return the sum of all even parent
     *
     * @param root the given TreeNode
     * @return the sum of all even parent
     */
    public static int sumEvenGrandparent(TreeNode root) {
        findSum(root);

        return ans;
    }

    /**
     * Helper method to recursively find the sum of all even parents
     *
     * @param t the given
     */
    public static void findSum(TreeNode t) {
        // Edge case: if the root is null, just return
        if (t == null) {
            return;
        }

        // If the node is even, sum the non-null children
        if (t.val % 2 == 0) {
            if (t.left != null) {
                if (t.left.left != null) {
                    ans += t.left.left.val;
                }

                if (t.left.right != null) {
                    ans += t.left.right.val;
                }
            }

            if (t.right != null) {
                if (t.right.left != null) {
                    ans += t.right.left.val;
                }

                if (t.right.right != null) {
                    ans += t.right.right.val;
                }
            }
        }

        findSum(t.left);
        findSum(t.right);
    }

    public static void main(String[] args) {

    }

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}